package medium

import (
	. "GoLeetcode/common"
	"sort"
)

/*
时间复杂度：O(NlogN)
空间复杂度：O(NlogN)

解决：双指针技巧，定义一个全局指针i，然后对worker和jobs均进行升序排序，
	遍历worker时，通过i指针去已排序的jobs中遍历直到遇到第一个大于skill的位置pos；
	通过maxProfit记录[0,pos]范围内最大的profit, 然后累加到ans；
	这样有一个好处，每次i都是到第一个jobs[i][0]>skill的位置停止，下次继续从上次停止的地方开始，
	这样处理起始只循环了N次，而不是N^2
*/

func maxProfitAssignment(difficulty []int, profit []int, worker []int) int {
	jobs := make([][2]int, len(difficulty))
	for i := range difficulty {
		jobs = append(jobs, [2]int{difficulty[i], profit[i]})
	}
	sort.Slice(jobs, func(i, j int) bool {
		return jobs[i][0] < jobs[j][0]
	})
	sort.Ints(worker)
	i := 0
	maxProfit := 0
	ans := 0
	for _, skill := range worker {
		for i < len(difficulty) && skill >= jobs[i][0] {
			maxProfit = Max(maxProfit, jobs[i][1])
			i++
		}
		ans += maxProfit
	}
	return ans
}
